package 简单.二分查找;

/**
 * 符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
 * <p>
 * arr.length >= 3
 * 存在 i（0 < i < arr.length - 1）使得：
 * arr[0] < arr[1] < ... arr[i-1] < arr[i]
 * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
 * 给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/B1IidL
 */
public class 山峰数组的顶部_069 {

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1};
        System.out.println(peakIndexInMountainArray2(arr));

    }

    /**
     * 遍历
     * 找出不是递增的最后一个元素
     *
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return i;
            }
        }
        return arr.length - 1;
    }

    /**
     * 双指针
     *
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray2(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (right >= 0 && left <= right) {
            if (arr[left] > arr[left + 1]) {
                return left;
            }
            if (arr[right] > arr[right - 1]) {
                return right;
            }
            left++;
            right--;
        }
        return right;
    }

    /**
     * 二分查找
     * 假设i索引所在的元素是最大值
     * <i的元素
     * 下一位元素比当前元素大
     * >i的元素
     * 下一位元素比当前元素小
     * 找出下一位元素比当前元素大的最大元素
     * 如果i<i+1,左边界收缩
     * i>i+1,右边界收缩
     *
     * @param arr
     * @return
     */
    public static int efficientPeakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                ans = mid + 1;
                //因为呈现递增趋势，mid左边的元素肯定比右边的小，排除
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

}
